package com.jxb.four;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import com.jxb.tree.TreeNode;

/**
 * 二叉树的层序遍历
 *
 * @author jiaobo
 * @date Created in 2024/12/31 22:37
 **/
public class BinTreeLevelOrderTraversal_102 {

    //基于队列来实现
    public List<List<Integer>> levelOrderWithQueue(TreeNode root) {
       //输出结果
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        //定义队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //获取每层的节点数
            int levelCount = queue.size();
            //每层的结果集
            List<Integer> subList = new ArrayList<>();
            //处理本层节点，并将左右子树进行入队
            for (int i = 0;i<levelCount;i++) {
                if (queue.peek().left != null) {
                    queue.offer(queue.peek().left);
                }
                if (queue.peek().right != null) {
                    queue.offer(queue.peek().right);
                }
                subList.add(queue.poll().val);
            }
        }
        return res;
    }

    //基于递归来实现
    //需要设置树高，来判断是哪一层的元素
    public List<List<Integer>> levelOrder(TreeNode root) {
        //输出结果
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        levelPreVisit(res, root, 0);
        return res;
    }

    private void levelPreVisit(List<List<Integer>> res, TreeNode root, int height) {
        if (root == null) {
            return;
        }
        if (height >= res.size()) {
            res.add(new ArrayList<>());
        }
        res.get(height).add(root.val);
        levelPreVisit(res,root.left,height+1);
        levelPreVisit(res,root.right,height+1);
    }

}
